import java.io.BufferedReader;
import java.io.InputStreamReader;


public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String stra = br.readLine();
		String strb = br.readLine();
		
		char[] arrayA = convertToCharArray(stra);
		char[] arrayB = convertToCharArray(strb);
		
		//int[][] memTable = new int[arrayA.length][arrayB.length];
		int[] memTable1 = new int[arrayA.length];
		int[] memTable2 = new int[arrayA.length];
//		for(int i = 0; i < arrayA.length; i++) {
//			memTable[i][0] = 0;
//		}
//		
//		for(int j = 0; j < arrayB.length; j++) {
//			memTable[0][j] = 0;
//		}
		
		for(int j = 1; j < arrayB.length; j++) {
			for(int i = 1; i < arrayA.length; i++) {
				if(arrayA[i] == arrayB[j]) {
					memTable2[i] = memTable1[i - 1] + 1; 
				} else {
					memTable2[i] = max(memTable1[i - 1], memTable1[i], memTable2[i - 1]);
				}
			}
			int[] tmp = memTable1;
			memTable1 = memTable2;
			memTable2 = tmp;
		}
		
//		for(int i = 1; i < arrayA.length; i++) {
//			for(int j = 1; j < arrayB.length; j++) {
//				if(arrayA[i] == arrayB[j]) {
//					memTable[i][j]  = memTable[i - 1][j - 1] + 1;
//				} else {
//					memTable[i][j] = max(memTable[i - 1][j - 1], memTable[i][j - 1], memTable[i - 1][j]);
//				}
//			}
//		}
		//System.out.println(findLCS(arrayA, arrayB, arrayA.length - 1, arrayB.length - 1));
		System.out.println(memTable1[arrayA.length - 1]);
	}
	
	private static int findLCS(char[] arrayA, char[] arrayB, int i, int j) {
		if(i == 0 || j == 0) {
			return 0;
		}
		if(arrayA[i] == arrayB[j]) {
			return findLCS(arrayA, arrayB, i - 1, j - 1) + 1;
		} else {
			return max(findLCS(arrayA, arrayB, i - 1, j - 1), findLCS(arrayA, arrayB, i - 1, j), findLCS(arrayA, arrayB, i, j - 1));
		}
	}
	
	private static int max(int i, int j, int k) {
		if(i > j && i > k) {
			return i;
		}
		if(j > k) {
			return j;
		}
		return k;
	}
	
	private static char[] convertToCharArray(String str) {
		char[] array = new char[str.length() + 1];
		array[0] = '\0';
		for(int i = 0; i < str.length(); i++) {
			array[i + 1] = str.charAt(i);
		}
		return array;
	}

}

